package com.sicheng.lc.杂题.滑动窗口专题;

import java.util.TreeSet;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/7/12 22:40
 */
public class 存在重复元素III {
    //https://leetcode.cn/problems/contains-duplicate-iii/
    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        // 窗口长度 k + 1, nums[i],nums[j]差距<=t
        // 红黑树 频繁查找和淘汰元素
        TreeSet<Long> tree = new TreeSet<>();
        for (int i = 0; i < nums.length; i++) {
            // 窗口左边界是否过期
            if (i > k) {
                tree.remove((long) nums[i - k - 1]);
            }
            //寻找大于等于nums[i]的最小元素
            Long x = tree.floor((long) nums[i]);
            //寻找小于等于nums[i]的最大元素
            Long y = tree.ceiling((long) nums[i]);
            if (x != null && nums[i] - x <= t)
                return true;
            if (y != null && y - nums[i] >= t)
                return true;

            tree.add((long) nums[i]);
        }

        return false;
    }
}
